/*
归并排序的思想
把原始数组拷贝到新的空间，
把一个数组一分二划分为两个有序数组，i指向第一个数组中的第一个元素，j指向第二个数组中第一个
两两比较，小的元素放入原始数组的
当第二个有序数组合并回去的时候，把第一个有序数组剩下的元素个数加到计数器中，
计数器的值即为所求
*/
class Solution {
public:
    int merge(vector<int>&num,int l,int r)
    {
        if(l>=r)
            return 0;
        int mid=l+(r-l)/2;
        int res=(merge(num, l, mid)+merge(num, mid+1, r))%1000000007;
        int i=l,j=mid+1;
        vector<int> tmp;
        while(i<=mid&&j<=r)
        {
            if(num[i]<=num[j]) //i所指的第一个有序区间的元素如果小于等于第二个有序区间，直接插入
            {tmp.push_back(num[i++]);}
            else//把第一个有序数组剩下的元素个数加到计数器
            {
                 tmp.push_back(num[j++]);
                (res+=mid-i+1)%=1000000007;
            }
        }
        //存在某个区间没有比较完
        while(i<=mid)
        {tmp.push_back(num[i++]);}
        while(j<=r)
        {
            tmp.push_back(num[j++]);
        }
        i=l;
        for(auto x:tmp)
        {
            num[i++]=x;
        }
        return res;
        
    }
    int InversePairs(vector<int> data) {
        return merge(data, 0, data.size()-1);
    }
};